package Top100;

import Algorithm.backtrack.*;
import Algorithm.comprehensive.sumofSubSequence.LMS.LMS_BackTrack;
import Algorithm.comprehensive.sumofSubSequence.LMS.LMS_Dynamic;
import Algorithm.dynamic.ChangeMoneyCombination_Dynamic;
import Algorithm.dynamic.ChangeMoneyPermutation_Dynamic;
import Algorithm.dynamic.ChangeMoney_Least_Dynamic;
import Algorithm.dynamic.CombinationNum_NonRepeat_Dynamic;
import DataStructure.stringOps.slidingWindow.ArrayPermutation_Sliding;
import DataStructure.tree.binaryTree.binaryTreeApply.BTFindCertainValuePath_Recursion;

/**
 * @author liujun
 * @version 1.0
 * @date 2021/1/15
 * @author—Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 全排列问题
 */

public interface ArrayPermutation extends BackTrack {

    default void ArrayPermutation() {

        // 数组的连续积 小于等于给定值的组合
        ArrayPermutationPlus aps = new ArrayPermutationPlus();
        ArrayPermutation_Sliding aps1 = new ArrayPermutation_Sliding();
        // 最大子段乘积(连续), 给定一个数组，求出这个数组最大连续的子段乘积
        LMS_Dynamic lms = new LMS_Dynamic();
        LMS_BackTrack lmsb = new LMS_BackTrack();

        // 二叉树中和为某一值的路径
        BTFindCertainValuePath_Recursion btr = new BTFindCertainValuePath_Recursion();

        // 数组中存在 等于给定值的组合 【数组 可以   无限重复的选择】
        CombinationNum_BackTrack cn = new CombinationNum_BackTrack();
        // 数组中存在 等于给定值的组合 【数组 不可以 无限重复的选择】
        CombinationNum_NonRepeat_BackTrack cnr = new CombinationNum_NonRepeat_BackTrack();
        CombinationNum_NonRepeat_Dynamic cnd = new CombinationNum_NonRepeat_Dynamic();

        // 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
        ChangeMoney_Least_BackTrack cm = new ChangeMoney_Least_BackTrack();
        ChangeMoney_Least_Dynamic cd = new ChangeMoney_Least_Dynamic();
        /*
        Tips：给一个数组和一个target，换零钱问题会演变出来以下：
        0、换成Target，是否可以凑出来 ：CombinationNum_Dynamic
        1、换成Target，所需要的最少零钱数量 ： ChangeMoney_Dynamic
        2、换成Target，输出所有的零钱排列【允许同一面值的零钱复用】【排列问题】 ：ChangeMoneyPermutation_BackTrack
        3、换成Target，输出所有不重复的零钱组合【允许同一面值的零钱复用】【组合问题】 ：ChangeMoneyCombination_BackTrack
        4、换成Target，输出所有不重复不复用的零钱组合【不允许同一面值的零钱复用】 ： CombinationNum_Dynamic
         */

        /*
        Tips：排列和组合的问题
        1、体现在Dynamic上是两层for循环，具体见 ChangeMoneyPermutation_Dynamic 和 ChangeMoneyCombination_Dynamic
        2、体现在BackTrack上是内层for的起始值，具体见 ChangeMoneyPermutation_BackTrack 和 ChangeMoneyCombination_BackTrack
         */
        ChangeMoneyPermutation_Dynamic cpd = new ChangeMoneyPermutation_Dynamic();
        ChangeMoneyCombination_Dynamic ccd = new ChangeMoneyCombination_Dynamic();
        ChangeMoneyPermutation_BackTrack cpb = new ChangeMoneyPermutation_BackTrack();
        ChangeMoneyCombination_BackTrack ccb = new ChangeMoneyCombination_BackTrack();
    }

    // 输出的 List 按照 List.size 从小到大 来排序
    int[][] getAnswer(int[] array, int target);

}
